Trying to apply PCCA+ to an Augmented Jump Chain

Main Idea

We use an Agent Based Model to simulate the Opinion Dynamics Problem. We then try to use the Agumented Jump Chain (AJC) to the simulation results obtained to get a generator for the jump process of agents between different influencers. We then try to apply PCCA+ to the resulting AJC to study the long-term clustering properties of the non-autonomous process of the Opinion Dynamics simulations.

The time-space discretization scheme used for the AJC implementation is as follows: time is discretized into the same intervals used in the ABM simulation (i.e. the ones resulting from the numerical integration procedure). These are constant, since non-adaptive integration methods are used for the simulation. The space discretization is not provided explicitly. The opinion space is partitioned into the “clicques” or “followings” of a given influencer. In other words, the jumps between boxes in state space are switches from one influencer to another. This defines an implicit partition of state space, as the relationship of followership between an agent and an influencer is (stochastically) determined by their distance to one another.

Some results

At each time step of the ABM simulation process we calculate the rate at which each influencer wins or loses followers (agents). These rates correspond to the rate of a jump process, one for each influencer, that determines the stochastic jumps a given agent might make from following one influencer to any other.

These rates are recorded at each time step during the integration procedure and stored in \(M\) matrices of shape \(I \times I\), or equivalently, in a \(I \times I \times M\) tensor. We refer to this tensor as \(R\), with “frames” \(R_k\) for \(k = 1, \dots, M\). Each \(R_k\) represents the jump rates for each influencer in the system at time \(k\).

Given a rate tensor \(R\) we can calculate the AJC either directly, or by transorming each rate matrix \(R_k\) to a probability transition matrix \(P_k\) by calculating the exponential of matrix \(R_k\). i.e. \(P_k = \exp(R_k)\).

In the following figure, we show the resulting AJC matrix calculated from rate matrices. Note how the logarithm of each entry is what is displayed. Given the properties of the AJC, the entries of the matrix decay with a speed that makes any pattern finding by color challenging, which is why the logarithm is shown.

ARM calculated with rate matrices, sub-normal trimmed.

In this image, the sub-normal numbers (i.e. those smaller than the machine epsilon for Floating Point 64 bit numbers) are trimmed and set explicitly to zero.

Changing the parameters in the simulation to affect how clusters form (e.g. by changing influencer friction and attractive forces) results in AJC matrices that “look” different, but it is difficult to quantify exactly how. I tried to find these similarites and differences by looking at other quantitative properties of the matrices, more on that on the next section. It is also worth noting that the resulting AJC matrices are almost never row-stochastic, and were thus normalized for the next stages of the experiments.

Whenever the AJC procedure is applied to probability transition matrices the resulting matrix is completely different from the one obtained by using rate matrices, even though the information is essentially the same. The resulting AJC obtained using rate matrices (we will refer to it as \(J_r\)) and the one obtained by converting those same rate matrices to probability transition matrices (henceforth denoted \(J_p\)) don’t even share the same broad structure. The entries of \(J_r\) decay rapidly as we get further away from the main diagonal, to the point where very soon these entries become sub-normal and are thus trimmed out of the final result. This is not the case in \(J_p\), the entries do decay but in what appears to be linear fashion. Note how the color depends on the magnitude of the entry, not on the logarithm of it as it dit for the previous graphic.

ARM calculated with probability transition matrices

Given that the implementation of the Augmented Jump Chain algorithm was tested against the canonical python version used to compute the results and produce the figures in the original paper, and proved to produce identical results, we have no reason to believe the algorithm is in some ways flawed. With this in mind we first procede to an examination of the matrices eigenvalues and the application of PCCA+ to them. Initially we tried going directly to PCCA+ but the matrices violate some condition that are requiered by the algorithm. More comments on this on the next section.

The challenges

Trying to quantify the properties of the computed ARMs we calculate their respective eigenvalues.

For the probability transition matrix version we can see how they behave:

Sorted eigenvalues of the probability ARM.

We can see the expected gap in eigenvalues, they are all real, and no one eigenvalue is greater than 1. However, they do not behave as we would expect the eigenvalues of a stochastic matrix to do. The largest eigenvalue is far from 1, and they are not always strictly positive. This is because the resulting ARM is not stochastic by any means (neither row nor column wise). It is not clear to me if this is normal, or if AJC should produce a row or column stochastic matrix.

When examining the eigenvalues of the ARM calculated with rate matrices we run into a problem: some eigenvalues have complex parts.

Sorted eigenvalues of the rate ARM.

Even though the imaginary part for these eigenvalues is commparatively small, there is still cause for concern. In theory, an ARM should not have complex eigenvalues.

Since the eigenvalues are sorted by magnitude it makes little sense to compare how similar or different the ARMs obtained via the two methods described by calculating the difference between eigenvalues. However, just to show how little resemblance they bear, Figure 1 shows the absolute difference between the eigenvalues of each ARM.

Figure 1: Difference of the (real part) of the eigenvalues for each ARM

The attempt

Disregarding for a moment the apparent problems described previously, we try to apply PCCA+ to the resulting ARMS. For this to not to be trivially flawed, we row-normalize both AR Matrices before feeding them into PCCA+.

When trying this, we run into an assertion error that is supposed to fail whenever the condtion: \[ (X^\top X) ./ \operatorname{size}(X, 1) \approx I \] where \(I\) is the identity matrix. Intuitively, this check seems to have something to do with the symmetry of the matrix that we try to apply PCCA+ on. However, formally, I don’t know where the condition comes from. Reviewing the theory about the procedure, I haven’t been able to concretely place or name the condition or why its violation is problematic.

After “symmetrizing” the ARM by multiplying it with it’s own tranpose produces a different matrix this is neither a rate nor a probability matrix, and thus, is not intended to be used as input to PCCA+.

Questions

  1. Is the entire approach of trying to use AJC to produce a generator for the jump process of an ABM and then using PCCA+ to study metastability inherently flawed and thus the failure of the pipeline is to be expected?

  2. Do the results of the AJC suggest a flaw of application, or a flaw of implementation? i.e, does the fact that something with complex (or negative) eigenvalues is resulting from the application of AJC to some rate or probability matrices suggest that the algorithm is implemented wrong?